package Alibaba;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2022-01-29 13:30
 *
 * 105. 从前序与中序遍历序列构造二叉树
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * 递归：通过先序遍历找到根节点，然后根据中序遍历找到左右子树的个数
 */
public class buildTree105 {

    TreeNode build(int[] preorder,int pre_start,int pre_end,int[] inorder,int in_start,int in_end){
        if (pre_start>pre_end||pre_end>=preorder.length||pre_start<0||in_start>in_end||in_start<0||in_end>=inorder.length){
            return null;
        }
        int rootVal=preorder[pre_start];
        int index=in_start;
        while (index<=in_end&&inorder[index]!=rootVal){
            index++;
        }
        int leftLen=index-in_start;
        TreeNode root=new TreeNode(rootVal);
        root.left=build(preorder,pre_start+1,pre_start+leftLen,inorder,in_start,index-1);
        root.right=build(preorder,pre_start+leftLen+1,pre_end,inorder,index+1,in_end);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
}
